﻿#ifndef __SS_ASCII_TRIE_TREE_H__
#define __SS_ASCII_TRIE_TREE_H__
#include "ssAsciiTrieNode.h"
#include "ssTrieTreeDef.h"
#include "../ssPair.h"
#include "../ssStack.h"
//#include "../../ssBaseDefine.h"

namespace StarSeeker
{

	template<typename T_VALUE, unsigned char T_KEY_NUM>
	class ssAsciiTrieTree
	{
	public:
		ssAsciiTrieTree();
		~ssAsciiTrieTree();
		ssAsciiTrieTree(const ssAsciiTrieTree& dic);
		void operator= (const ssAsciiTrieTree& dic);

		//查找
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* Find(const char* arr, u32 len);
		//插入
		ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t> Insert(ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* parent, char k, T_VALUE* val);
		ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t> Insert(const char* arr, u32 len, T_VALUE* val);
		//删除
		error_t Remove(ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* node);
		error_t Remove(const char* arr, u32 len);
		//返回节点数
		u32 GetCount() { return m_count; }
		//清空树
		void Clear();
		//遍历
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* Begin();
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* Next();
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* End();
	private:
		//复制对象
		void CopyFrom(const ssAsciiTrieTree& dic);
		//遍历复制
		void RecursionCopy(const ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* itr, ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* parent);
		//寻找左边的兄弟
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* LeftBrother(ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* node);
		//寻找右边的兄弟
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* RightBrother(ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* node);
		//寻找第一个子节点
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* FirstChild(ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* node);
	private:
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>					m_root;
		u32													m_count;
		ssNumStack<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*>	m_stack;
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*				m_iterator;
	};

	template<typename T_VALUE,  unsigned char T_KEY_NUM>
	inline ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::ssAsciiTrieTree()
	{
		m_root.m_pOnwer = this;
		m_count = 0;
		m_iterator = 0;
	}

	template<typename T_VALUE,  unsigned char T_KEY_NUM>
	inline ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::~ssAsciiTrieTree()
	{
		Clear();
	}

	template<typename T_VALUE,  unsigned char T_KEY_NUM>
	inline ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::ssAsciiTrieTree(const ssAsciiTrieTree & dic)
	{
		m_root.m_pOnwer = this;
		m_count = 0;
		CopyFrom(dic);
	}

	template<typename T_VALUE,  unsigned char T_KEY_NUM>
	void ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::operator=(const ssAsciiTrieTree& dic)
	{
		Clear();
		CopyFrom(dic);
	}

	template<typename T_VALUE,  unsigned char T_KEY_NUM>
	inline ssAsciiTrieNode<T_VALUE, T_KEY_NUM> * ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::Find(const char* arr, u32 len)
	{
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* node = &m_root;
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* temp = 0;
		for (u32 i = 0; i < len; i++)
		{
			node = node->Find(arr[i]);
			if (!node)
			{
				return 0;
			}
		}
		return node;
	}

	template<typename T_VALUE,  unsigned char T_KEY_NUM>
	inline ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t> ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::Insert(ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* parent, char k, T_VALUE * val)
	{
		if (parent && parent->m_pOnwer==this)
		{
			if (k<0 || k>=T_KEY_NUM)
			{
				return ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t>(0, SS_DICT_KEY_ILLEGAL);
			}
			ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* node = parent->m_children[k];
			if (node)
			{
				return ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t>(node, SS_DICT_KEY_EXISTED);
			}
			ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* newNode = new ssAsciiTrieNode<T_VALUE, T_KEY_NUM>;
			newNode->m_pParent = parent;
			newNode->m_pOnwer = this;
			newNode->m_key = k;
			newNode->m_pValue = val;
			if (!parent->AddChild(k, newNode))
			{
				delete newNode;
				return ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t>(0, SS_DICT_CREATE_NODE_FAILED);
			}
			++m_count;
			return ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t>(newNode, SS_DICT_OK);
		}
		return ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t>(0, SS_DICT_NODE_ILLEGAL);
	}

	template<typename T_VALUE,  unsigned char T_KEY_NUM>
	inline ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t> ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::Insert(const char* arr, u32 len, T_VALUE* val)
	{
		if (arr==0 || len==0)
		{
			return ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t>(0, SS_DICT_KEY_ILLEGAL);
		}
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* node = &m_root;
		for (u32 i = 0; i < len; i++)
		{
			if (arr[i] < 0 || arr[i] >= T_KEY_NUM)
			{
				return ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t>(0, SS_DICT_KEY_ILLEGAL);
			}
			ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* temp = node->m_children[arr[i]];
			if (temp)
			{
				node = temp;
				if (i == len - 1)
					return ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t>(node, SS_DICT_KEY_EXISTED);
			}
			else
			{
				ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* newNode = new ssAsciiTrieNode<T_VALUE, T_KEY_NUM>;
				newNode->m_pParent = node;
				newNode->m_pOnwer = this;
				newNode->m_key = arr[i];
				if (i == len - 1)
					newNode->m_pValue = val;

				if (!node->AddChild(arr[i], newNode))
				{
					delete newNode;
					return ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t>(0, SS_DICT_CREATE_NODE_FAILED);
				}
				node = newNode;
			}
		}
		++m_count;
		return ssPair<ssAsciiTrieNode<T_VALUE, T_KEY_NUM>*, error_t>(node, SS_DICT_OK);
	}

	template<typename T_VALUE,  unsigned char T_KEY_NUM>
	error_t StarSeeker::ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::Remove(ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* node)
	{
		if (node == 0)
		{
			return SS_DICT_KEY_NOTEXISTED;
		}
		if (node->m_pOnwer != this)
		{
			return SS_DICT_DEL_ILLEGAL;
		}
		if (node->m_pParent == 0)
		{
			return SS_DICT_DEL_ILLEGAL;
		}
		if (node->m_count==0)//叶节点
		{
			ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* parent = node->m_pParent;
			while (node && parent)
			{
				if (!parent->DelChild(node->m_key))
				{
					return SS_DICT_DEL_ILLEGAL;
				}
				delete node;
				node = parent;
				if (node)
				{
					parent = node->m_pParent;
				}
				if (node->m_count>0 || node->m_pValue)
				{
					break;
				}
			}
		}
		else
		{
			if (node->m_pValue)
			{
				delete node->m_pValue;
				node->m_pValue = 0;
			}
		}
		--m_count;
		return SS_DICT_OK;
	}

	template<typename T_VALUE,  unsigned char T_KEY_NUM>
	inline error_t ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::Remove(const char* arr, u32 len)
	{
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* node = Find(arr, len);
		return Remove(node);
	}

	template<typename T_VALUE,  unsigned char T_KEY_NUM>
	inline void ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::Clear()
	{
		m_count = 0;
		m_root.Clear();
	}

	template<typename T_VALUE, unsigned char T_KEY_NUM>
	inline ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::Begin()
	{
		m_stack.Empty();
		m_iterator = &m_root;
		return Next();
	}

	template<typename T_VALUE, unsigned char T_KEY_NUM>
	inline ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::Next()
	{
		ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* ret = 0;
		while (m_iterator != 0 || m_stack.Count())
		{
			if (m_iterator != 0)
			{
				m_stack.Push(m_iterator);
				m_iterator = FirstChild(m_iterator);
			}
			else
			{
				m_iterator = ret = *m_stack.Pop();
				m_iterator = RightBrother(m_iterator);
				break;
			}
		}
		return ret;
	}

	template<typename T_VALUE, unsigned char T_KEY_NUM>
	inline ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::End()
	{
		return 0;
	}

	template<typename T_VALUE,  unsigned char T_KEY_NUM>
	inline void ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::CopyFrom(const ssAsciiTrieTree & dic)
	{
		RecursionCopy(&dic.m_root, &m_root);
	}

	template<typename T_VALUE,  unsigned char T_KEY_NUM>
	inline void ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::RecursionCopy(const ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* itr, ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* parent)
	{
		if (itr)
		{
			T_VALUE* pValue = 0;
			if (itr->m_pValue)
			{
				pValue = new T_VALUE;
				*pValue = *itr->m_pValue;
			}
			Insert(parent, itr->m_key, pValue);
			if (itr->m_count>0)
			{
				for (int i = 0; i < T_KEY_NUM; i++)
				{
					if (itr->m_children[i])
					{
						RecursionCopy(itr->m_children[i], itr);
					}

				}
			}
		}
	}

	template<typename T_VALUE, unsigned char T_KEY_NUM>
	inline ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::LeftBrother(ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* node)
	{
		if (node->m_pParent && node->m_pOnwer==this && node->m_key>0)
		{
			for (unsigned char i = node->m_key-1; i > 0; i--)
			{
				if (node->m_pParent->m_children[i])
				{
					return node->m_pParent->m_children[i];
				}
			}
		}
		return 0;
	}

	template<typename T_VALUE, unsigned char T_KEY_NUM>
	inline ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::RightBrother(ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* node)
	{
		if (node->m_pParent && node->m_pOnwer == this && node->m_key < T_KEY_NUM)
		{
			for (unsigned char i = node->m_key+1; i < T_KEY_NUM; i++)
			{
				if (node->m_pParent->m_children[i])
				{
					return node->m_pParent->m_children[i];
				}
			}
		}
		return 0;
	}

	template<typename T_VALUE, unsigned char T_KEY_NUM>
	inline ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* ssAsciiTrieTree<T_VALUE, T_KEY_NUM>::FirstChild(ssAsciiTrieNode<T_VALUE, T_KEY_NUM>* node)
	{
		if (node->m_pOnwer == this && node->m_count>0)
		{
			for (unsigned char i = 0; i < T_KEY_NUM; i++)
			{
				if (node->m_children[i])
				{
					return node->m_children[i];
				}
			}
		}
		return 0;
	}
}
#endif
